package cn.bellychang.leetcode.question235;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 *
 * Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.
 *
 * According to the definition of LCA on Wikipedia:
 * “The lowest common ancestor is defined between two nodes p and q as the lowest node in T
 * that has both p and q as descendants (where we allow a node to be a descendant of itself).”
 *
 * @author ChangLiang
 * @date 2021/2/8
 */
public class Solution {

    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {


        Deque<TreeNode> stackP = new ArrayDeque<>();
        Deque<TreeNode> stackQ = new ArrayDeque<>();

        TreeNode temp = root;
        while (temp.val != p.val) {
            stackP.push(temp);
            if (temp.val > p.val) {
                temp = temp.left;
            } else {
                temp = temp.right;
            }
        }
        stackP.push(temp);

        TreeNode temp2 = root;
        while (temp2.val != q.val) {
            stackQ.push(temp2);
            if (temp2.val > q.val) {
                temp2 = temp2.left;
            } else {
                temp2 = temp2.right;
            }
        }
        stackQ.push(temp2);

        int min = Math.min(stackP.size(), stackQ.size());
        while (stackP.size() > min) {
            stackP.pop();
        }
        while (stackQ.size() > min) {
            stackQ.pop();
        }
        while (min != 0) {
            TreeNode popP = stackP.pop();
            TreeNode popQ = stackQ.pop();
            if (popP.val == popQ.val) {
                return popP;
            }
            min--;
        }
        return null;
    }
}
